编译原理(五) LL(1)文法分析法(预测分析表的构造算法C++实现) |
您所在的位置：网站首页 › 预测分析表 编译原理 › 编译原理(五) LL(1)文法分析法(预测分析表的构造算法C++实现) |
编译原理(五) LL(1)文法分析法(预测分析表的构造算法C++实现)
|
令Ｇ是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为：
FIRST(α)={a | α=>*a…, a∈VT}
若α=>*ε，则规定ε∈FIRST(α)
FIRST(α)是α的所有可能推导的开头终结符或可能的ε
如果非终结符Ａ的所有候选首符集两两不相交，即Ａ的任何两个不同候选αi和αｊ
FIRST(αi) ∩FIRST(αj)=Φ
那么当要求Ａ匹配输入串时，Ａ就能根据它所面临的第一个输入符号ａ，准确的指派某一个候选前去执行任务。这个候选就是那个终结首符集含ａ的α。
FOLLOW(A)
:
假定S是文法G的开始符号，对于G的任何非终结符A，我们定义
FOLLOW(A)={a | S=>*…Aa…，a∈VT}
FOLLOW(A)是所有句型中出现在紧接A之后的终结符或“#”。开始符号的FOLLOW集初始化时加入“#”。
当非终结符A面临输入符号a，且a不属于A的任意候选首符集但A的某个候选首符集包含ε时，只有当a∈FOLLOW(A)时，才可能允许A自动匹配。
LL(1)文法
:
文法不含左递归
对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→α1 |α2 | … |αn，则FIRST(αi)∩FIRST(αj)=Φ (i≠j)
对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则，FIRST(A)∩FOLLOW(A)=Φ
如果一个文法G满足以上条件，则称该文法G为LL(1)文法。
LL(1)文法是不带回溯的自顶向下的文法
预测分析表：
预测分析表示一个M[A,a]形式的矩阵。其中A为非终结符，a是终结符或‘#’ 。
矩阵元素M[A,a]中存放着一条关于A的产生式，指出当A面临输入符号a时所应采用的候选。
M[A,a]中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。
预测分析表的构造
FIRST(α)的构造算法
要构造FIRST(α) ，根据定义： α=X1⋯Xn 那么对于从前到后的Xi我们进行分类讨论： 如果Xi∈Vt,那么FIRST(α)=FIRST(Xi)={Xi} 如果Xi∈Vn,因为不存在左递归，所以Xi=a.......|ϵ,那么FIRST(Xi)={a,ϵ,FIRST(Xi+1)} 只要Xi−1不包含ϵ,那么Xi不可能影响FIRST(α) 那么我们通过记录每个a∈V ,然后进行深度优先记忆化搜索,将所有的状态填满，因为LL(1)文法使不会回溯的，所以能够保证在O(n)的时间完成 ，采取递归的形式实现 FIRST(α)的构造实现代码 #include #include #include #include #include #include #include #include #include #include #define MAX 507 using namespace std; //大写字母为非终止符(可以多一个'的标号做区分)，小写字母为终止符,用~代替epsilon class WF { public: string left; set right; WF ( char s[] ) { left = s; } void print ( ) { printf ( "%s->" , left.c_str() ); set::iterator it = right.begin(); if ( right.begin()!= right.end() ) { printf ( "%s" , it->c_str() ); it++; } for(; it != right.end() ; it++ ) printf ( "|%s" , it->c_str() ); puts(""); } void insert ( char s[] ) { right.insert ( s ); } }; map first; map follow; map VN_dic; vector VN_set; bool used[MAX]; void dfs ( int x ) { if ( used[x] ) return; used[x] = 1; string& left = VN_set[x].left; set& right = VN_set[x].right; set::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) for ( int i = 0 ; i < it->length() ; i++ ) { if ( !isupper( it->at(i) ) && it->at(i) != '\'' ) { first[left].insert ( it->at(i) ); break; } if ( isupper( it->at(i) ) ) { int y; if ( i != it->length()-1 && it->at(i+1) == '\'' ) y = VN_dic[it->substr(i,2)]-1; else y = VN_dic[it->substr(i,1)]-1; string& tleft = VN_set[y].left; dfs ( y ); set& temp = first[tleft]; set::iterator it1 = temp.begin(); bool flag = true; for ( ; it1 != temp.end() ; it1++ ) { if ( *it1 == '~' ) flag = false; first[left].insert( *it1 ); } if ( flag ) break; } else continue; } } void make_first ( ) { memset ( used , 0 , sizeof ( used ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) dfs ( i ); #define DEBUG #ifdef DEBUG map::iterator it = first.begin(); for ( ; it != first.end() ; it++ ) { printf ( "FIRST(%s)={" , it->first.c_str() ); set & temp = it->second; set::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } int main ( ) { int n; char s[MAX]; while ( ~scanf ( "%d" , &n ) ) { for ( int i = 0 ; i < n ; i++ ) { scanf ( "%s" , s ); int len = strlen ( s ),j; for ( j = 0 ; j < len ; j++ ) if ( s[j] == '-' ) break; s[j] = 0; if ( !VN_dic[s] ) { VN_set.push_back ( s ); VN_dic[s] = VN_set.size(); } int x = VN_dic[s]-1; VN_set[x].insert ( s+j+2 ); } make_first(); } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136Input:
设S,A,B∈Vn,那么连续使用如下规则，直至follow集不再发生变化： （1） S为标识符，那么FOLLOW(S)包含“#” （2） 若A::=αBβ,那么FOLLOW(B)+=FIRST(B)−{ϵ} （3） 若A::=αB或者A::=αBβ,且β⇒∗ϵ，那么FOLLOW(B)+=FOLLOW(A) FOLLOW(A)的构造实现代码 #include #include #include #include #include #include #include #include #include #include #define MAX 507 using namespace std; //大写字母为非终止符(可以多一个'的标号做区分)，小写字母为终止符,用~代替epsilon class WF { public: string left; set right; WF ( char s[] ) { left = s; } void print ( ) { printf ( "%s->" , left.c_str() ); set::iterator it = right.begin(); if ( right.begin()!= right.end() ) { printf ( "%s" , it->c_str() ); it++; } for(; it != right.end() ; it++ ) printf ( "|%s" , it->c_str() ); puts(""); } void insert ( char s[] ) { right.insert ( s ); } }; map first; map follow; map VN_dic; vector VN_set; bool used[MAX]; void dfs ( int x ) { if ( used[x] ) return; used[x] = 1; string& left = VN_set[x].left; set& right = VN_set[x].right; set::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) for ( int i = 0 ; i < it->length() ; i++ ) { if ( !isupper( it->at(i) ) && it->at(i) != '\'' ) { first[left].insert ( it->at(i) ); break; } if ( isupper( it->at(i) ) ) { int y; if ( i != it->length()-1 && it->at(i+1) == '\'' ) y = VN_dic[it->substr(i,2)]-1; else y = VN_dic[it->substr(i,1)]-1; string& tleft = VN_set[y].left; dfs ( y ); set& temp = first[tleft]; set::iterator it1 = temp.begin(); bool flag = true; for ( ; it1 != temp.end() ; it1++ ) { if ( *it1 == '~' ) flag = false; first[left].insert( *it1 ); } if ( flag ) break; } else continue; } } void make_first ( ) { memset ( used , 0 , sizeof ( used ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) dfs ( i ); #define DEBUG #ifdef DEBUG puts ("***************FIRST集***********************"); map::iterator it = first.begin(); for ( ; it != first.end() ; it++ ) { printf ( "FIRST(%s)={" , it->first.c_str() ); set & temp = it->second; set::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } void append ( const string& str1 , const string& str2 ) { set& from = follow[str1]; set& to = follow[str2]; set::iterator it = from.begin(); for ( ; it != from.end() ; it++ ) to.insert ( *it ); } void make_follow ( ) { while ( true ) { bool goon = false; for ( int i = 0 ; i < VN_set.size() ; i++ ) { string& left = VN_set[i].left; set& right = VN_set[i].right; set::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) { bool flag = true; const string& str = *it; for ( int j = it->length()-1 ; j >= 0 ; j-- ) { if ( str[j] == '\'' ) { int x = VN_dic[it->substr(j-1,2)]-1; if ( flag ) { int tt = follow[it->substr(j-1,2)].size(); append ( left , it->substr(j-1,2) ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[x].right.count("~" ) ) flag = false; } for ( int k = j+1 ; k < it->length() ; k++ ) { if ( isupper(str[k]) ) { string id; if ( k != it->length()-1 && str[k+1] == '\'' ) id = it->substr(k,2); else id = it->substr(k,1); set& from = first[id]; set& to = follow[it->substr(j-1,2)]; int tt = to.size(); set::iterator it1 = from.begin(); for ( ; it1 != from.end() ; it1++ ) if ( *it1 != '~' ) to.insert ( *it1 ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[VN_dic[id]-1].right.count("~") ) break; } else if ( str[k] != '\'' ) { |
Output:
【本文地址】
今日新闻 |
推荐新闻 |